/*
 * BiThrTree.c
 *
 *  Created on: 2011-12-6
 *      Author: tracl01
 */

#include "predefine.h"
//#include "BiTree.c"
typedef enum { Link, Thread}PointerTag;	//书写应当注意
typedef struct BiThrNode{
	Elemtype data;
	struct BiThrNode *lchild,*rchild;
	PointerTag	Ltag,Rtag;
}BiThrNode,*BiThrTree;

int createBiThrTree(BiThrTree *T){		//这个结点元素输入很有意思，不能每输入一个元素回车一次
	Elemtype ch;					//而要输入完所有组成二叉树的元素再回车
	scanf("%c",&ch);
	if (ch == ' ') {				//这里根据数据类型自定义一字符或整数
		*T = NULL;
	} else {
		*T = (BiThrTree)malloc(sizeof(BiThrNode));
		if (!*T) {
			exit(EXIT_FAILURE);
		}
		(*T)->data = ch;
		createBiThrTree(&((*T)->lchild));	//需要这样书写,*T要加上括号
		if (!((*T)->lchild)) {
			(*T)->Ltag = Link;
		}
		createBiThrTree(&((*T)->rchild));
		if (!(*T)->rchild) {
			(*T)->Rtag = Link;
		}
	}
	return EXIT_SUCCESS;
}

/*
 * 下面这三个函数极难，需要理解的细节非常多，并且很透彻****************
 * */
void inThreading(BiThrTree p, BiThrTree pre){
	if (p) {
		inThreading(p->lchild, pre);
		if (!p->lchild) {
			p->Ltag = Thread; p->lchild = pre;
		}
		if (!pre->rchild) {
			p->Rtag = Thread; pre->rchild = p;
		}
		pre = p;
		inThreading(p->rchild, pre);
	}
}

int inorderThreading(BiThrTree *Thrt, BiThrTree T){
	if (!(*Thrt = (BiThrTree)malloc(sizeof(BiThrNode)))) {
		exit(EXIT_FAILURE);
	}
	BiThrTree pre = *Thrt;
	(*Thrt)->Ltag = Link;	(*Thrt)->Rtag = Thread;	//因为头结点只有左孩子——根结点
	(*Thrt)->lchild = (*Thrt);	//右指针为什么要回指呢？
	if (!T) {
		(*Thrt)->lchild = (*Thrt);
	} else {
		(*Thrt)->lchild = T;
		inThreading(T, pre);
		pre->rchild = *Thrt;	pre->Rtag = Thread;
		(*Thrt)->rchild = pre;
	}
	return EXIT_SUCCESS;
}

void visitt(Elemtype e){
	printf("%c ", e);
};

int inorderTraverse_Thr(BiThrTree T){
	BiThrTree p = T->lchild;
	printf("81");
	while(p != T){
		printf("83");
		while(p->Rtag == Link)	p = p->lchild;
		visitt(p->data);
		while(p->Rtag == Thread && p->rchild != T){
			p = p->rchild; visitt(p->data);
		}
		p = p->rchild;
	}
	return EXIT_SUCCESS;
}

int main(void){
	BiThrTree T,Thrt;
	createBiThrTree(&T);
	printf("success\n");
	inorderThreading(&Thrt, T);
	printf("sucess\n");
	inorderTraverse_Thr(T);
	printf("sucess");
	return EXIT_SUCCESS;
}
